package algorithm.difficult;

import java.util.List;
import java.util.Stack;
import java.util.ArrayList;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: Calculate224
 * @description: 实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
 *
 *224. 基本计算器
 *
 * 示例 1：
 *
 * 输入：s = "1 + 1"
 * 输出：2
 *
 * 示例 2：
 *
 * 输入：s = " 2-1 + 2 "
 * 输出：3
 *
 * 示例 3：
 *
 * 输入：s = "(1+(4+5+2)-3)+(6+8)"
 * 输出：23
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/basic-calculator
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/3/1010:35
 * @since V1.0
 */
public class Calculate224 {

    public static void main(String[] args) {

        System.out.println( new Calculate224().calculate("-1+2"));
    }

    //栈 逆波兰表达式 计算器
    public int calculate(String s) {
        Stack<String> temp = new Stack<String>();
        Stack<String> stack = new Stack<String>();
        List<String> init = init(s);
        if (init.get(0).equals("-")){
            init.add(0,"0");
        }
        for (String item:init){
            if (item.equals("(")){
                temp.push(item);
            }else if(item.equals("-")||item.equals("+")){
                while (!temp.isEmpty() && !temp.peek().equals("(")){
                    stack.push(temp.pop());
                }
                temp.push(item);
            }else if (item.equals(")")){
                while (!temp.isEmpty()){
                    String pop = temp.pop();
                    if (pop.equals("(")){
                        break;
                    }else {
                        stack.push(pop);
                    }
                }
            }else {
                stack.push(item);
            }
        }
        while (!temp.isEmpty()){
            stack.push(temp.pop());
        }
        System.out.println(stack);
        return  calc(stack);
    }

    public List<String> init(String s){
        String str = s.replace(" ", "");
        List<String> list =  new ArrayList<>();
        int n=0;
        for (int i=0;i<str.length();i++){
            if (str.charAt(i) == '+'||str.charAt(i) == '-'||str.charAt(i) == '(' ||str.charAt(i) == ')'){
                //符号
                if (!str.substring(n,i).equals("")){
                    list.add(str.substring(n,i));
                }
                list.add(str.charAt(i)+"");
                n=i+1;
            }
        }
        if (!str.substring(n).equals("")){
            list.add(str.substring(n));
        }
        System.out.println(list);
        return list;
    }

    public int calc(List<String> list){
        Stack<Integer> stack = new Stack<>();
        for (String x:list){
            if (x.equals("+")){
                stack.push(stack.pop()+stack.pop());
            }else if(x.equals("-")){
                stack.push(-stack.pop()+stack.pop());
            }else {
                stack.push(Integer.parseInt(x));
            }
        }
        return stack.pop();
    }
}
